package com.melo.graph;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc BFS广度优先图搜索类
 * @date 2025-04-23
 */
public class BfsGraph extends FsGraph {

    public BfsGraph(int vertexNum) {
        super(vertexNum);
    }

    /**
     * BFS广度优先搜索
     */
    public void bfs() {
        for (int i = 0; i < getVertexNum(); i++) {
            if (!getVisitFlagArr()[i]) {
                // 遍历所有的结点，进行BFS回溯
                bfs(i);
            }
        }
    }

    /**
     * BFS广度优先搜索
     *
     * @param vertexIndex 顶点的下标
     */
    private void bfs(int vertexIndex) {
        Queue<Integer> queue = new ArrayDeque<>();
        // 访问结点
        System.out.print(getVertexByIndex(vertexIndex) + "=>");
        // 将结点设置为已经访问
        getVisitFlagArr()[vertexIndex] = true;

        queue.add(vertexIndex);
        while (!queue.isEmpty()) {
            // 取出队列的头结点下标
            Integer queueHeadVertexIndex = queue.poll();
            // 查找结点的第一个邻接结点
            int neighborIndex = getFirstNeighbor(queueHeadVertexIndex);
            while (neighborIndex != -1) {
                if (!getVisitFlagArr()[neighborIndex]) {
                    System.out.print(getVertexByIndex(neighborIndex) + "=>");
                    getVisitFlagArr()[neighborIndex] = true;

                    queue.add(neighborIndex);
                }

                neighborIndex = getNextNeighbor(queueHeadVertexIndex, neighborIndex);
            }
        }
    }
}
